package com.tgy.leetcode;

import java.util.Arrays;
import java.util.Stack;

/**
 * @Author: tgy
 * @Date: 12/3/20 10:10 AM
 */
public class 查找当前位置向前向后的第一个最大值 {


    public void findPreNextFirstMax(int[] nums) {

        if (nums == null) {

            return;
        }

        int[] leftFirstMaxs = new int[nums.length];
        int[] rightFirstMaxs = new int[nums.length];

        for (int i = 0; i < nums.length; i++) {

            leftFirstMaxs[i] = rightFirstMaxs[i] = -1;
        }

        int index;
        for (int i = 1; i < nums.length; i++) {


            index = i - 1;

            while (index >= 0) {

                if (nums[i] < nums[index]) {

                    leftFirstMaxs[i] = index;
                    break;
                }else {
                    // 从 index 位置往左没有最大值
                    if (leftFirstMaxs[index] == -1) {

                        break;
                    }
                }
                index = leftFirstMaxs[index];
            }
        }

        System.out.println(Arrays.toString(leftFirstMaxs));

        for (int i = nums.length - 2; i >= 0 ; i--) {

            index = i + 1;

            while (index < nums.length) {

                if (nums[i] < nums[index]) {

                    rightFirstMaxs[i] = index;
                    break;
                }else {

                    if (rightFirstMaxs[index] < 0) {

                        break;
                    }
                }

                index = rightFirstMaxs[index];
            }
        }

        System.out.println(Arrays.toString(rightFirstMaxs));


    }

    public void findPreNextMax(int[] nums) {

        if (nums == null || nums.length == 0) {

            return;
        }

        // 构造一个单调递减栈
        Stack<Integer> stack = new Stack<>();

        int[] leftMaxIndexs = new int[nums.length];
        int[] rightMaxIndexs = new int[nums.length];

        for (int i = 0; i < nums.length; i++) {

            leftMaxIndexs[i] = -1;
            rightMaxIndexs[i] = -1;
        }

        // 3,2,5,7,1,2,6

        for (int i = 0; i < nums.length; i++) {


            if (stack.isEmpty()) {

                stack.push(i);
                continue;
            }

            if (nums[stack.peek()] >= nums[i]) {

                leftMaxIndexs[i] = stack.peek();
            }else {

                while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {

                    rightMaxIndexs[stack.pop()] = i;
                }

                if (!stack.isEmpty()) {

                    leftMaxIndexs[i] = stack.peek();
                }
            }

            stack.push(i);
        }

        System.out.println(Arrays.toString(leftMaxIndexs));
        System.out.println(Arrays.toString(rightMaxIndexs));
    }
}
